public class PartitionList {
    public ListNode partition(ListNode head, int x) {
        ListNode l1 = new ListNode(), last1 = l1;
        ListNode l2 = new ListNode(), last2 = l2;

        // 尾插
        while(head != null) {
            // 将原链表中每个节点独立出来, 防止产生环
            ListNode next = head.next;
            head.next = null;
            if(head.val < x) {
                // 小于 x 尾插在 l1 后面
                last1.next = head;
                last1 = last1.next;
            }else {
                // head.val >= x
                // 大于等于 x 尾插在 l2 后面
                last2.next = head;
                last2 = last2.next;
            }
            head = next;
        }

        // 两个链表尾首相连
        last1.next = l2.next;
        return l1.next;
    }
}
